package datastructures.list.doublylist;


/**
 * 双向链表
 *
 * @author hck
 */
public class DoublyLinkedList<T> {
    /**
     * 链表头
     */
    private Node head;
    /**
     * 链表尾
     */
    private Node tail;
    /**
     * 链表当前长度
     */
    private int size;

    public DoublyLinkedList() {
    }

    public void add(T data) {
        Node last = tail;
        Node node = new Node(tail, data, null);
        tail = node;
        if (head == null) {
            head = node;
        } else {
            last.next = node;
        }
        size++;
    }

    public T get(int index) {
        Node node = getNodeByIndex(index);
        return node == null ? null : node.getData();
    }

    public T remove(int index) {
        checkIndex(index);
        if (size == 0) {
            throw new IllegalArgumentException("empty list!");
        }
        Node prefix = null;
        Node current = null;
        Node next = null;
        if (index == 0) {
            current = head;
            next = head.next;
            head = next;
        } else {
            current = getNodeByIndex(index);
            prefix = current.prefix;
            next = current.next;
            prefix.next = next;
            if (next != null) {
                next.prefix = prefix;
            } else {
                tail = prefix;
            }
        }
        size--;
        return current.getData();
    }

    public void print() {
        if (size == 0) {
            System.out.println("[]");
        }
        System.out.print("[");
        Node index = head;
        for (int i = 0; i < size; i++) {
            System.out.print(index.getData());
            if (i != size - 1) {
                System.out.print(",");
            }
            index = index.next;
        }
        System.out.println("]");
    }

    private void checkIndex(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
    }

    private Node getNodeByIndex(int index) {
        checkIndex(index);
        if (size == 0) {
            return null;
        }
        //  由于是包含头尾节点
        //  那么可以判断index离头节点还是尾节点比较近
        //  来决定是从头遍历还是从尾遍历
        int middle = size / 2;
        if (index < middle) {
            Node node = head;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {
            Node node = tail;
            //  size 是数组元素个数, 这里是遍历游标,所以i需要减一
            for (int i = size - 1; index < i; i--) {
                node = node.prefix;
            }
            return node;
        }
    }

    /**
     * data node
     */
    private class Node {
        private T data;
        private Node prefix;
        private Node next;

        Node(Node prefix, T data, Node next) {
            this.prefix = prefix;
            this.data = data;
            this.next = next;
        }

        T getData() {
            return data;
        }
    }
}
